package main

import "fmt"

func quickSortEntry2(arr []int) {
	quickSort2(arr, 0, len(arr)-1)
}

func quickSort2(s []int, l, r int) {
	if l < r {
		q := partition2(s, l, r)

		fmt.Printf("quickSort2|l=%v|r=%v|q=%v|\n", l, r, q)

		quickSort2(s, l, q-1)
		quickSort2(s, q+1, r)
	}

}

//@brief 快速排序--单边循环法
//		单边循环 主流程
//			1、arr[startIndex] （第一个元素） 用作基准元素（值为 pivot）；
//			2、从 startIndex+1 ~ endIndex 遍历数组
//				值小于 pivot 的从 startIndex+1 （含 startIndex+1） 依次填入元素(元素swap/元素交换)；
//				每填入一个元素（元素swap/元素交换），mark下标指向该元素；
//				所以 mark的取值范围是   [startIndex+1 , endIndex]；
//			3、遍历完成后， startIndex  和 mark 交换
//			4、返回 mark ，供后续拆分数组用
//				拆分成两个数组， arr1 和 arr2 ；
//				arr1下标取值范围 [startIndex, mark]；
//				arr2下标取值范围 [mark+1, endIndex]；
//				arr1任意元素，都比 arr2任意元素小，arr1和arr2 按以上 1~4 做遍历，这样就能完成排序；
//		举例
//			待排序数组
//				arrInit:[3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8]
//			第一轮处理
//			从 strtIndex+1 ~ endIndex （第一轮为 len(arr)-1 )遍历数组，值小于 pivot （第一轮值为 3） 的依次填入元素(元素swap/元素交换)
//				arrInit:[3 1 1 2 2 2 2 0 2 3 5 8 9 7 9 3 5 3 8 4 6 9 6 4 3 3 8 3 4 7 9 5 6 5 8 8]
//				此时 mark为8， 对应的值为 2
//			第一个元素和 mark指向的元素交换 后的数组，此时 partition2 已经处理完毕；返回 mark 8；
//				arrInit:[2 1 1 2 2 2 2 0 3 3 5 8 9 7 9 3 5 3 8 4 6 9 6 4 3 3 8 3 4 7 9 5 6 5 8 8]
//			后续拆分 arrInit为两个 数组  arr1[2 1 1 2 2 2 2 0 3]  和 arr2[3 5 8 9 7 9 3 5 3 8 4 6 9 6 4 3 3 8 3 4 7 9 5 6 5 8 8]
//				下来用 partition2 递归处理 arr1 和 arr2

func partition2(arr []int, startIndex, endIndex int) int {
	var (
		mark  = startIndex
		pivot = arr[startIndex]
		point = startIndex + 1
	)

	// fmt.Printf("partition2 start|pivot=%v\n", pivot)

	for point < len(arr) {
		if arr[point] < pivot {
			// fmt.Printf("	swap|arr[%v]=%v|arr[%v]=%v\n", point, arr[point], mark, arr[mark])
			mark++
			arr[mark], arr[point] = arr[point], arr[mark]

			// fmt.Printf("		arr|arr=%v\n", arr)
		}
		point++
	}

	arr[startIndex], arr[mark] = arr[mark], arr[startIndex]

	// fmt.Printf("point=%v|\n", point)
	return mark
}

func main() {
	fmt.Printf("quickSort start\n")

	arrInit := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8}
	fmt.Printf("arrInit:%v\n", arrInit)

	quickSortEntry2(arrInit)
	fmt.Printf("arrInit:%v\n", arrInit)
}
